1. Field of the Invention
The present invention relates to memory addressing, and more particularly to addressing for circular buffers used in digital systems, like digital signal processors.
2. Description of Related Art
Circular addressing, also called modulo addressing, is commonly used in digital signal processing and other data processing applications. In a circular buffer for which circular addressing is applied, an address extent is assigned to the buffer. In generating addresses for the circular buffer, a current address is incremented by an offset value to produce a next address. If the sum of the current address and the offset value points to an address outside of the assigned address extent, then the next address wraps around to the opposite boundary of the circular buffer.
Various approaches to generating addresses for circular buffers have been applied in prior art. One common way to accomplish circular addressing is to define two explicit parameters that set the upper and lower boundaries of the assigned address extent. In this way, the user has flexibility to define a buffer with an unlimited position in the available memory. However, this approach requires registers to store the boundaries and relatively complicated logic to calculate the next address. As address generation can be in the critical path of a particular design, it is desirable to reduce the number of parameters required and to simplify the logic.
Another approach for generating addresses for circular buffers is described in U.S. Pat. No. 4,800,524, invented by Roesgen. In the approach of the Roesgen patent, the buffer is defined by a single buffer length parameter and a current address for the circular buffer. The lower boundary of the circular buffer is implied from the current address and the buffer length by substituting the lower N bits of the current address with zeros, where xe2x80x9cNxe2x80x9d is the bit position of the leading (left most) 1 in the binary representation of the buffer length. The upper boundary of the circular buffer is defined as the implied lower boundary plus the buffer length. This approach is simpler to implement than the approach requiring explicit parameters that set the upper and lower boundaries. However, memory usage is not as efficient, because of the limited set of boundaries available.
Other approaches in the prior art for circular address generation are described in U.S. Pat. No. 4,202,035, invented by Lane; U.S. Pat. No. 4,809,156, invented by Taber; U.S. Pat. No. 5,249,148, invented by Catherwood, et al.; and U.S. Pat. No. 5,381,360, invented by Shridhar, et al.
As the complexity of digital signal processing applications which rely on circular addressing has grown, the need for improving the flexibility and reducing the cost of address generators for such applications is growing.
The present invention provides an apparatus that generates addresses for circular address buffers in a memory, in which a higher boundary of a circular buffer is implied from the current address. This approach can be applied alone, and in combination with circular buffers which rely on an implied lower boundary to improve memory usage and flexibility in the design of circular buffers for integrated circuits and processing systems.
One embodiment of an address generator according to the present invention comprises inputs that receive a current address A, an address offset M, a buffer length L and a control signal; and logic configured to compute a first memory address and a second memory address for locations in the memory in response to A, M, and L. One of the first and second memory addresses is provided in response to the control signal. The first memory address corresponds the current address A plus the address offset M for a first circular buffer having an implied lower address boundary X and including addresses X through (X+L). The second memory address corresponds the current address A plus the address offset M for a second circular buffer having an implied higher address boundary Y and comprising addresses Y through (Yxe2x88x92L).
The buffer length, L, is value that when expressed in binary has a leading 1 at bit position N. The implied lower address boundary X is computed by replacing the lower N bits of current address A with 0""s. The implied higher address boundary Y is computed by replacing the lower N bits of current address A with 1""s.
In various embodiments, said inputs include registers storing A, M and L. The control signal can also be stored in a register, or stored within the register which is shared with one of the other parameters, such as the offset value M.
In one embodiment, the logic used by the address generator includes a first adder to produce a s first output equal to a sum A+M with a carry out signal; and a second adder to produce a second output equal to a first wrap address sum (A+M)xe2x88x92(L+1) when the sign of M is positive or a second wrap address sum (A+M)+(L+1) when the sign of M is negative, with a carry out signal. Select logic selects the first output or the second output in response to the carry out signals from the first and second adders. The first and second adders are shared logic, used for circular buffers with the implied lower address boundary and for circular buffers with the implied higher address boundary, in one preferred embodiment.
In yet other embodiments, where L has a leading 1 at bit position N, the implied lower address boundary X is computed by replacing the lower N bits of current address A with 0""s, and the implied higher address boundary Y is computed by replacing the lower N bits of current address A with 1""s. The first and second adders produce carry out signals for multiple bit positions, and a selector is responsive to L to provide the carry out from the Nth bit position in the adder for use by the logic. Thus, in this embodiment the select logic is operable to select the first output or the second output in response to the carry out signals from the Nth bit position in the first and second adders.
For embodiments in which both the implied lower address boundary and implied higher address boundary circular buffers are used, the select logic is configured:
to select the output of the first adder
if control signal is set for the first memory address, the address offset is positive, and the carry out from neither the first adder nor the second adder is 1, or
if control signal is set for the first memory address, the address offset is negative, and the carry out from the first adder is 1, or
if the control signal is set for the second memory address, the address offset is positive, and the carry out from the first adder is 0, or
if the control signal is set for the second memory address, the address offset is negative, and the carry outs from both the first adder and the second adder are 1; and
to select the output of the second adder
if the control signal is set for the first memory address, the address offset is positive, and the carry out from at least one of the first adder or the second adder is 1, or
if the control signal is set for the first memory address, the address offset is negative, and the carry out from the first adder is 0, or
if the control signal is set for the second memory address, the address offset is positive, and the carry out from the first adder is 1, or
if the control signal is set for the second memory address, the address offset is negative, and the carry out from at least one of the first adder or the second adder is 0.
For embodiments in which only the implied higher address boundary is used, the select logic is configured:
to select the output of the first adder
if the address offset is positive, and the carry out from the first adder is 0, or
if the address offset is negative, and the carry outs from both the first adder and the second adder are 1; and
to select the output of the second adder
if the address offset is positive, and the carry out from the first adder is 1, or
if the address offset is negative, and the carry out from at least one of the first adder or the second adder is 0.
The present invention is also embodied by an integrated circuit that includes a processor core, register files that store in the current address A, offset value M and buffer length L, memory and address generators for the memory. In embodiments according to the present invention the address generator is configured to use only the implied higher address boundary, or to use a combination of the implied higher address boundary and implied lower address boundary, as described above.
Other aspects and advantages of the present invention are described below with reference to the figures.